package problem354;

import java.util.Arrays;

class Solution2 {
    public int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;
        int[] dp = new int[n];
        dp[0] = 1;
        int ret = 1;
        Arrays.fill(dp,1);
        Arrays.sort(envelopes,(a,b)->a[0]-b[0]);
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<n; j++) {
                if(envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) {
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
        }
        for(int i = 0; i<n; i++) {
            System.out.print(dp[i]+" ");
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }
}

/*
dp[i]: 以第i个信封为结尾的对多个数
*/